import numpy as np
import math


# t,r 为矩阵
def distDtw(t, r):
    # 求矩阵行数
    n = t.size
    m = r.size
    # 帧匹配距离矩阵
    d = np.zeros([n, m])
    for i in range(n):
        for j in range(m):
            d[i, j] = (t[i] - r[j])**2

    # 累积距离矩阵
    realMax = np.finfo(float).max
    D = np.ones([n, m]) * realMax
    D[0, 0] = d[0, 0]
    # 动态规划
    for i in range(1, n):
        for j in range(m):
            D1 = D[i-1, j]
            if j > 0:
                D2 = D[i-1, j-1]
            else:
                D2 = realMax

            if j > 2:
                D3 = D[i-1, j-2]
            else:
                D3 = realMax

            D[i, j] = d[i, j] + min([D1, D2, D3])

    return math.sqrt(D[n-1, m-1])